#include<iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:

    void getout(ListNode* start) {
        while (start != nullptr) {
            std::cout << start->val << " ";
            start = start->next;
        }
        std::cout << "#" << std::endl;
    }

    bool isPalindrome(ListNode* head) {
        if (head == nullptr) return false;
        if (head->next == nullptr) return true;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* ppre = slow;
        while (fast != nullptr && fast->next != nullptr) {
            ppre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
    //    std::cout << slow->val << " " <<( fast == nullptr )<< "/n";
        ListNode* pre = slow;
    
        ListNode* now = slow->next;
        ListNode* pro;
        pre->next = nullptr;
        while (now != nullptr) {
            pro = now->next;
            now->next= pre;
            pre = now;
            now = pro;
        }

       // getout(head);
       // getout(pre);
       // getout(pre);

        ListNode* left = head;
        ListNode* right = pre;

        bool res = true;
        while (left != nullptr && right != nullptr) {
            if (left->val != right->val) {
                res = false;
                break;
            }
            left = left->next;
            right = right->next;
        }
        std::cout << res << " ";

        now = pre->next;
        pre->next = nullptr;
        while (now != nullptr) {
            std::cout << now->val;
            pro = now->next;
            now->next = pre;
            pre = now;
            now = pro;
        }
        ppre->next = pre;
        getout(head);
        return res;
    }
};
